/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

//求根的两个节点的路径，反过来的第一个交点就是公共祖先
//可以用栈来存储路径
class Solution {
    bool find(TreeNode* root, TreeNode* p, stack<TreeNode*>& st)
    {
        if (root == nullptr)
            return false;

        st.push(root);
        if (root == p)
            return true;
        
        if(find(root->left, p, st))
            return true; 

        if (find(root->right, p, st))
            return true;
        
        st.pop();

        return false;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> st_p, st_q;
        find(root, p, st_p);
        find(root, q, st_q);

        //删到相同的长度
        while (st_p.size() != st_q.size())
        {
            st_p.size() > st_q.size() ? st_p.pop() : st_q.pop();
        }

        //同时删，第一个相等的就是最近公共祖先
        while (true)
        {
            if (st_p.top() == st_q.top())
                return st_p.top();
            
            st_p.pop();
            st_q.pop();
        }
        return nullptr;
    }
};